/*-------------------------------------------------------------------------
 *
 * ts_typanalyze.c
 *	  从tsvector列收集统计信息的函数
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  src/backend/tsearch/ts_typanalyze.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "catalog/pg_collation.h"
#include "catalog/pg_operator.h"
#include "commands/vacuum.h"
#include "common/hashfn.h"
#include "tsearch/ts_type.h"
#include "utils/builtins.h"


/* 词素的哈希键 */
typedef struct
{
	char	   *lexeme;			/* 词素（不是空字符终止的！） */
	int			length;			/* 其字节长度 */
} LexemeHashKey;

/* lossy counting 算法的哈希表条目 */
typedef struct
{
	LexemeHashKey key;			/* 这是 LC 算法中的 'e'。 */
	int			frequency;		/* 这是 'f'。 */
	int			delta;			/* 这是 'delta'。 */
} TrackItem;

static void fc_compute_tsvector_stats(VacAttrStats *fc_stats,
								   AnalyzeAttrFetchFunc fc_fetchfunc,
								   int fc_samplerows,
								   double fc_totalrows);
static void fc_prune_lexemes_hashtable(HTAB *fc_lexemes_tab, int fc_b_current);
static uint32 fc_lexeme_hash(const void *fc_key, Size fc_keysize);
static int	fc_lexeme_match(const void *fc_key1, const void *fc_key2, Size fc_keysize);
static int	fc_lexeme_compare(const void *fc_key1, const void *fc_key2);
static int	fc_trackitem_compare_frequencies_desc(const void *fc_e1, const void *fc_e2,
											   void *fc_arg);
static int	fc_trackitem_compare_lexemes(const void *fc_e1, const void *fc_e2,
									  void *fc_arg);


/*
 *	ts_typanalyze -- tsvector 列的自定义 typanalyze 函数
 */
Datum ts_typanalyze(PG_FUNCTION_ARGS)
{
	VacAttrStats *fc_stats = (VacAttrStats *) PG_GETARG_POINTER(0);
	Form_pg_attribute fc_attr = fc_stats->attr;

	/* 如果 attstattarget 列为负值，则使用默认值 */
	/* 注意：在 stats->attr 上涂写是可以的，因为这是一个副本 */
	if (fc_attr->attstattarget < 0)
		fc_attr->attstattarget = default_statistics_target;

	fc_stats->compute_stats = fc_compute_tsvector_stats;
	/* 有关 minrows 选择的评论见 commands/analyze.c */
	fc_stats->minrows = 300 * fc_attr->attstattarget;

	PG_RETURN_BOOL(true);
}

/*
 *	compute_tsvector_stats() -- 计算tsvector列的统计信息
 *
 *	该函数计算对于确定@@操作的选择性以及非空行的比例和平均宽度有用的统计信息。
 *
 *	与我们为大多数数据类型所做的寻找最常见的值不同，我们在寻找最常见的词素。这更有用，因为两个行具有相同的tsvector的可能性非常小，因此在这种数据类型下MCV的概念有些不合适。通过获得最常见的词素列表，我们可以更好地判断@@选择性。
 *
 *	出于同样的原因，我们在确定不同值的数量时假设tsvector列是唯一的。
 *
 *	使用的算法是损失计数（Lossy Counting），如G. S. Manku和R. Motwani在论文《Approximate frequency counts over data streams》中所提出，该论文发表于2002年8月，在香港举办的第28届国际大数据大会上的4.2节。论文可在http://www.vldb.org/conf/2002/S10P03.pdf找到。
 *
 *	损失计数（即LC）算法如下：
 *	设s为项目的阈值频率（我们感兴趣的最小频率），epsilon为频率的误差范围。设D为一组三元组(e, f, delta)，其中e是元素值，f是该元素的频率（实际是其当前出现计数），delta是f的最大误差。我们从D为空开始，按大小为w的批次处理元素。（批次大小也称为“桶大小”，等于1/epsilon。）设当前批次编号为b_current，从1开始。对于每个元素e，如果它已经在D中，我们增加其f计数，否则插入一个新三元组到D中，值为(e, 1, b_current - 1)。处理完每个批次后，我们修剪D，从中删除所有f + delta <= b_current的元素。在算法完成后，我们抑制所有不满足f >= (s - epsilon) * N的元素，N是输入中元素的总数。我们发出剩余元素的估计频率f/N。LC论文证明该算法会找到所有真实频率至少为s的元素，并且没有频率被高估或低估超过epsilon。此外，在对输入分布的合理假设下，所需的表大小不会超过大约7倍的w。
 *
 *	我们将s设为自然语言频率表中第K个单词的估计频率，其中K是MCELEM数组中目标条目数量加上一个任意常量，目的是反映任何语言中最常见的单词通常是停止词，因此我们实际上不会在输入中看到它们。我们假设单词频率（包括停止词）的分布遵循Zipf定律，指数为1。
 *
 *	假设Zipfian分布，第K个单词的频率等于1/(K * H(W))，其中H(n)为1/2 + 1/3 + ... + 1/n，W是语言中的单词数量。将W设为一百万，我们大致得到0.07/K。假设前10个单词是停止词，得到s = 0.07/(K + 10)。我们设epsilon = s/10，这给出桶宽度w = (K + 10)/0.007以及最大期望哈希表大小约为1000 * (K + 10)。
 *
 *	注意：在上述讨论中，s、epsilon和f/N是指词素在所有输入词素中频率的比例。然而，我们实际上想在最终的pg_statistic条目中存储的是每个词素在其出现的所有行中的频率。假设输入的tsvectors正确构造，无词素在每个tsvector中出现超过一次，因此最终计数f是其出现的输入tsvectors数量的正确估计，我们只需将除数从N更改为nonnull_cnt即可得到我们想要的数字。
 */
static void fc_compute_tsvector_stats(VacAttrStats *fc_stats,
					   AnalyzeAttrFetchFunc fc_fetchfunc,
					   int fc_samplerows,
					   double fc_totalrows)
{
	int			fc_num_mcelem;
	int			fc_null_cnt = 0;
	double		fc_total_width = 0;

	/* 这是LC算法中的D。 */
	HTAB	   *fc_lexemes_tab;
	HASHCTL		fc_hash_ctl;
	HASH_SEQ_STATUS fc_scan_status;

	/* 这是来自LC算法的当前桶编号 */
	int			fc_b_current;

	/* 这是来自LC算法的'w' */
	int			fc_bucket_width;
	int			fc_vector_no,
				fc_lexeme_no;
	LexemeHashKey fc_hash_key;
	TrackItem  *fc_item;

	/*
	 * 我们希望在MCELEM数组中统计 statistics_target * 10 个语素。这个
	 * 倍数相当任意，但旨在反映在pg_statistic中跟踪的单个语素值的数量
	 * 应该多于简单标量列的值数量。
	 */
	fc_num_mcelem = fc_stats->attr->attstattarget * 10;

	/*
	 * 我们将桶宽度设置为(num_mcelem + 10) / 0.007，按照上述评论。
	 */
	fc_bucket_width = (fc_num_mcelem + 10) * 1000 / 7;

	/*
	 * 创建哈希表。它将位于本地内存中，因此我们不需要担心初始大小溢出。
	 * 同时，我们不需要关注锁定和内存管理。
	 */
	fc_hash_ctl.keysize = sizeof(LexemeHashKey);
	fc_hash_ctl.entrysize = sizeof(TrackItem);
	fc_hash_ctl.hash = fc_lexeme_hash;
	fc_hash_ctl.match = fc_lexeme_match;
	fc_hash_ctl.hcxt = CurrentMemoryContext;
	fc_lexemes_tab = hash_create("Analyzed lexemes table",
							  fc_num_mcelem,
							  &fc_hash_ctl,
							  HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);

	/* 初始化计数器。 */
	fc_b_current = 1;
	fc_lexeme_no = 0;

	/* 遍历tsvectors。 */
	for (fc_vector_no = 0; fc_vector_no < fc_samplerows; fc_vector_no++)
	{
		Datum		fc_value;
		bool		fc_isnull;
		TSVector	fc_vector;
		WordEntry  *fc_curentryptr;
		char	   *fc_lexemesptr;
		int			fc_j;

		vacuum_delay_point();

		fc_value = fc_fetchfunc(fc_stats, fc_vector_no, &fc_isnull);

		/*
		 * 检查空值/非空值。
		 */
		if (fc_isnull)
		{
			fc_null_cnt++;
			continue;
		}

		/*
		 * 累加宽度以计算平均宽度。由于它是一个
		 * tsvector，我们知道它是varlena。正如常规
		 * compute_minimal_stats函数中所示，我们使用吐司宽度进行此
		 * 计算。
		 */
		fc_total_width += VARSIZE_ANY(DatumGetPointer(fc_value));

		/*
		 * 如果需要，现在去除tsvector的吐司。
		 */
		fc_vector = DatumGetTSVector(fc_value);

		/*
		 * 我们循环遍历tsvector中的语素，并将它们添加到我们的
		 * 跟踪哈希表中。
		 */
		fc_lexemesptr = STRPTR(fc_vector);
		fc_curentryptr = ARRPTR(fc_vector);
		for (fc_j = 0; fc_j < fc_vector->size; fc_j++)
		{
			bool		fc_found;

			/*
			 * 构建哈希键。此时，该键指向(detoasted)
			 * tsvector值，但如果创建了新条目，我们
			 * 将其复制一份。这样我们可以在处理完所有
			 * 语素后释放tsvector值。
			 */
			fc_hash_key.lexeme = fc_lexemesptr + fc_curentryptr->pos;
			fc_hash_key.length = fc_curentryptr->len;

			/* 在哈希表中查找当前语素，如果是新语素则添加 */
			fc_item = (TrackItem *) hash_search(fc_lexemes_tab,
											 (const void *) &fc_hash_key,
											 HASH_ENTER, &fc_found);

			if (fc_found)
			{
				/* 该语素已在跟踪列表中 */
				fc_item->frequency++;
			}
			else
			{
				/* 初始化新的跟踪列表元素 */
				fc_item->frequency = 1;
				fc_item->delta = fc_b_current - 1;

				fc_item->key.lexeme = palloc(fc_hash_key.length);
				memcpy(fc_item->key.lexeme, fc_hash_key.lexeme, fc_hash_key.length);
			}

			/* lexeme_no是处理的元素数量（即N） */
			fc_lexeme_no++;

			/* 我们在处理每个桶后修剪D结构 */
			if (fc_lexeme_no % fc_bucket_width == 0)
			{
				fc_prune_lexemes_hashtable(fc_lexemes_tab, fc_b_current);
				fc_b_current++;
			}

			/* 前进到tsvector中的下一个WordEntry */
			fc_curentryptr++;
		}

		/* 如果向量被吐司化，释放去吐司后的副本。 */
		if (TSVectorGetDatum(fc_vector) != fc_value)
			pfree(fc_vector);
	}

	/* 只有在找到一些非空值的情况下，我们才能计算真实的统计数据。 */
	if (fc_null_cnt < fc_samplerows)
	{
		int			fc_nonnull_cnt = fc_samplerows - fc_null_cnt;
		int			fc_i;
		TrackItem **fc_sort_table;
		int			fc_track_len;
		int			fc_cutoff_freq;
		int			fc_minfreq,
					fc_maxfreq;

		fc_stats->stats_valid = true;
		/* 进行简单的空值比例和平均宽度统计 */
		fc_stats->stanullfrac = (double) fc_null_cnt / (double) fc_samplerows;
		fc_stats->stawidth = fc_total_width / (double) fc_nonnull_cnt;

		/* 假设这是一个唯一的列（见上述备注） */
		fc_stats->stadistinct = -1.0 * (1.0 - fc_stats->stanullfrac);

		/*
		 * 构建一个有趣的哈希表项数组，即
		 * 那些满足截止频率(s - epsilon)*N的项。还要识别
		 * 这些项中的最小和最大频率。
		 *
		 * 由于epsilon = s/10且bucket_width = 1/epsilon，因此截止
		 * 频率为9*N / bucket_width。
		 */
		fc_cutoff_freq = 9 * fc_lexeme_no / fc_bucket_width;

		fc_i = hash_get_num_entries(fc_lexemes_tab);	/* 足够的空间 */
		fc_sort_table = (TrackItem **) palloc(sizeof(TrackItem *) * fc_i);

		hash_seq_init(&fc_scan_status, fc_lexemes_tab);
		fc_track_len = 0;
		fc_minfreq = fc_lexeme_no;
		fc_maxfreq = 0;
		while ((fc_item = (TrackItem *) hash_seq_search(&fc_scan_status)) != NULL)
		{
			if (fc_item->frequency > fc_cutoff_freq)
			{
				fc_sort_table[fc_track_len++] = fc_item;
				fc_minfreq = Min(fc_minfreq, fc_item->frequency);
				fc_maxfreq = Max(fc_maxfreq, fc_item->frequency);
			}
		}
		Assert(fc_track_len <= fc_i);

		/* 输出一些用于调试的统计信息 */
		elog(DEBUG3, "tsvector_stats: target # mces = %d, bucket width = %d, "
			 "# lexemes = %d, hashtable size = %d, usable entries = %d",
			 fc_num_mcelem, fc_bucket_width, fc_lexeme_no, fc_i, fc_track_len);

		/*
		 * 如果我们获得的语素数量超过了我们真正想要的，去掉那些
		 * 频率最低的。最简单的方法是对数组按降序进行qsort并截断数组。
		 */
		if (fc_num_mcelem < fc_track_len)
		{
			qsort_interruptible(fc_sort_table, fc_track_len, sizeof(TrackItem *),
								fc_trackitem_compare_frequencies_desc, NULL);
			/* 将minfreq重置为我们保留的最小频率 */
			fc_minfreq = fc_sort_table[fc_num_mcelem - 1]->frequency;
		}
		else
			fc_num_mcelem = fc_track_len;

		/* 生成MCELEM插槽条目 */
		if (fc_num_mcelem > 0)
		{
			MemoryContext fc_old_context;
			Datum	   *fc_mcelem_values;
			float4	   *fc_mcelem_freqs;

			/*
			 * 我们想要存储按词素值排序的统计信息，首先按长度排序，然后按字节逐字节比较。首先进行长度比较的原因是我们不在乎排序，只要它是一致的，而首先比较长度给了我们避免调用 strncmp() 的机会。
			 *
			 * 这与我们处理标量统计信息的方式不同——它们是按频率排序的。原因是我们通常在寻找特定值时会搜索最常见的元素，因此可以获取它的频率。当值是预先排序时，我们可以对其采用二分搜索。请参见 ts_selfuncs.c 以获取实际使用场景。
			 */
			qsort_interruptible(fc_sort_table, fc_num_mcelem, sizeof(TrackItem *),
								fc_trackitem_compare_lexemes, NULL);

			/* 必须将目标值复制到anl_context中 */
			fc_old_context = MemoryContextSwitchTo(fc_stats->anl_context);

			/*
			 * 我们按词素值排序了统计信息，但我们希望能够在不遍历所有值的情况下找出最小和最大频率。我们在 mcelem_freqs 中的两个额外单元中保留这两个额外的频率。
			 *
			 * （注意：MCELEM 统计插槽定义允许一个额外的数字包含空值的频率，但我们不为 tsvector 列创建该数字，因为空元素是不可能的。）
			 */
			fc_mcelem_values = (Datum *) palloc(fc_num_mcelem * sizeof(Datum));
			fc_mcelem_freqs = (float4 *) palloc((fc_num_mcelem + 2) * sizeof(float4));

			/*
			 * 请参见上面的评论，以非空计数作为最终频率估计的除数。
			 */
			for (fc_i = 0; fc_i < fc_num_mcelem; fc_i++)
			{
				TrackItem  *fc_item = fc_sort_table[fc_i];

				fc_mcelem_values[fc_i] =
					PointerGetDatum(cstring_to_text_with_len(fc_item->key.lexeme,
															 fc_item->key.length));
				fc_mcelem_freqs[fc_i] = (double) fc_item->frequency / (double) fc_nonnull_cnt;
			}
			fc_mcelem_freqs[fc_i++] = (double) fc_minfreq / (double) fc_nonnull_cnt;
			fc_mcelem_freqs[fc_i] = (double) fc_maxfreq / (double) fc_nonnull_cnt;
			MemoryContextSwitchTo(fc_old_context);

			fc_stats->stakind[0] = STATISTIC_KIND_MCELEM;
			fc_stats->staop[0] = TextEqualOperator;
			fc_stats->stacoll[0] = DEFAULT_COLLATION_OID;
			fc_stats->stanumbers[0] = fc_mcelem_freqs;
			/* 请参见上述关于两个额外频率字段的评论 */
			fc_stats->numnumbers[0] = fc_num_mcelem + 2;
			fc_stats->stavalues[0] = fc_mcelem_values;
			fc_stats->numvalues[0] = fc_num_mcelem;
			/* 我们正在存储文本值 */
			fc_stats->statypid[0] = TEXTOID;
			fc_stats->statyplen[0] = -1;	/* typlen，-1 表示 varlena */
			fc_stats->statypbyval[0] = false;
			fc_stats->statypalign[0] = 'i';
		}
	}
	else
	{
		/* 我们只找到空值；假设该列完全为空 */
		fc_stats->stats_valid = true;
		fc_stats->stanullfrac = 1.0;
		fc_stats->stawidth = 0;	/* "unknown" */
		fc_stats->stadistinct = 0.0;	/* "unknown" */
	}

	/*
	 * 我们不需要清理任何临时的 palloc。哈希表也应该被清除，因为它使用了子内存上下文。
	 */
}

/*
 *  从 Lossy Counting 算法中修剪 D 结构的函数。
 *  请参阅 compute_tsvector_stats() 以获取更详细的解释。
 */
static void fc_prune_lexemes_hashtable(HTAB *fc_lexemes_tab, int fc_b_current)
{
	HASH_SEQ_STATUS fc_scan_status;
	TrackItem  *fc_item;

	hash_seq_init(&fc_scan_status, fc_lexemes_tab);
	while ((fc_item = (TrackItem *) hash_seq_search(&fc_scan_status)) != NULL)
	{
		if (fc_item->frequency + fc_item->delta <= fc_b_current)
		{
			char	   *fc_lexeme = fc_item->key.lexeme;

			if (hash_search(fc_lexemes_tab, (const void *) &fc_item->key,
							HASH_REMOVE, NULL) == NULL)
				elog(ERROR, "hash table corrupted");
			pfree(fc_lexeme);
		}
	}
}

/*
 *  词素的哈希函数。它们是字符串，但不是以 NULL 结尾的，因此我们需要一个特殊的哈希函数。
 */
static uint32 fc_lexeme_hash(const void *fc_key, Size fc_keysize)
{
	const LexemeHashKey *fc_l = (const LexemeHashKey *) fc_key;

	return DatumGetUInt32(hash_any((const unsigned char *) fc_l->lexeme,
								   fc_l->length));
}

/*
 *  用于词素的匹配函数，用于哈希表查找。
 */
static int fc_lexeme_match(const void *fc_key1, const void *fc_key2, Size fc_keysize)
{
	/* keysize 参数是多余的，键存储了它们的长度 */
	return fc_lexeme_compare(fc_key1, fc_key2);
}

/*
 *  词素的比较函数。
 */
static int fc_lexeme_compare(const void *fc_key1, const void *fc_key2)
{
	const LexemeHashKey *fc_d1 = (const LexemeHashKey *) fc_key1;
	const LexemeHashKey *fc_d2 = (const LexemeHashKey *) fc_key2;

	/* 首先，按长度进行比较 */
	if (fc_d1->length > fc_d2->length)
		return 1;
	else if (fc_d1->length < fc_d2->length)
		return -1;
	/* 长度相等，逐字节比较 */
	return strncmp(fc_d1->lexeme, fc_d2->lexeme, fc_d1->length);
}

/*
 *  用于按频率（降序排序）对 TrackItems 进行排序的比较器
 */
static int fc_trackitem_compare_frequencies_desc(const void *fc_e1, const void *fc_e2, void *fc_arg)
{
	const TrackItem *const *fc_t1 = (const TrackItem *const *) fc_e1;
	const TrackItem *const *fc_t2 = (const TrackItem *const *) fc_e2;

	return (*fc_t2)->frequency - (*fc_t1)->frequency;
}

/*
 *  用于对 TrackItems 按词素进行排序的比较器
 */
static int fc_trackitem_compare_lexemes(const void *fc_e1, const void *fc_e2, void *fc_arg)
{
	const TrackItem *const *fc_t1 = (const TrackItem *const *) fc_e1;
	const TrackItem *const *fc_t2 = (const TrackItem *const *) fc_e2;

	return fc_lexeme_compare(&(*fc_t1)->key, &(*fc_t2)->key);
}
